'''
https://leetcode.cn/problems/house-robber-iv/
'''
from functools import cache, lru_cache
from typing import List


class Solution:

    def minCapability(self, nums: List[int], k: int) -> int:
        n = len(nums)
        @lru_cache(maxsize=n)
        # 能偷多少间房子，在 capacity 的能力下(capacity >= nums[i])
        #       不能偷相邻的房子
        def f(i, capacity):
            if i >= n:
                return 0
            r1 = f(i + 1, capacity)
            r2 = 0
            if capacity >= nums[i]:
                r2 = 1 + f(i + 2, capacity)
            return max(r1, r2)

        l, r = 0, max(nums)
        ans = float('inf')
        while l <= r:
            m = (l + r) // 2
            if f(0, m) >= k:
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans

    def minCapability2(self, nums: List[int], k: int) -> int:
        n = len(nums)
        def f(capacity):
            dp = [0] * (n + 2)
            for i in range(n-1, -1, -1):
                dp[i] = dp[i + 1]
                if capacity >= nums[i]:
                    dp[i] = max(dp[i], 1 + dp[i + 2])
            return dp[0]
        l, r = 0, max(nums)
        ans = float('inf')
        while l <= r:
            m = (l + r) // 2
            if f(m) >= k:
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans

    def minCapability3(self, nums: List[int], k: int) -> int:
        n = len(nums)
        def f(capacity):
            a = b = 0
            for i in range(n-1, -1, -1):
                c = a
                if capacity >= nums[i]:
                    c = max(c, 1 + b)
                a, b = c, a
            return a
        l, r = min(nums), max(nums)
        ans = float('inf')
        while l <= r:
            m = (l + r) // 2
            if f(m) >= k:
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans

    def minCapability4(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 贪心：能偷就偷
        def f(capacity):
            res = 0
            i = 0
            while i < n:
                if capacity >= nums[i]:
                    res += 1
                    i += 1
                i += 1
            return res
        l, r = min(nums), max(nums)
        ans = float('inf')
        while l <= r:
            m = (l + r) // 2
            if f(m) >= k:
                ans = m
                r = m - 1
            else:
                l = m + 1
        return ans
